package com.yiwenup.struct._01_linear.array;

import com.yiwenup.struct._01_linear.base.AbstractList;

/**
 * 动态数组：实现数组的动态扩容
 * 缺点：动态扩容会造成内存空间的浪费
 */
@SuppressWarnings("unchecked")
public class DynamicArray<E> extends AbstractList<E> {

    /**
     * 元素数组
     */
    private E[] elements;

    private static final int DEFAULT_CAPACITY = 10;

    private static final int ELEMENT_NOT_FOUND = -1;

    public DynamicArray(int capacity) {
        capacity = Math.max(capacity, DEFAULT_CAPACITY);
        this.elements = (E[]) new Object[capacity];
    }

    public DynamicArray() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * 清空所有元素
     */
    public void clear() {
        for (int i = 0; i < this.size; i++) {
            this.elements[i] = null;
        }
        this.size = 0;
    }


    /**
     * 获取idx位置的元素
     *
     * @param idx 索引位置
     * @return 元素
     */
    public E get(int idx) {
        if (idx < 0 || idx >= this.size) {
            throw new IndexOutOfBoundsException("Index:" + idx + ", Size:" + this.size);
        }
        return this.elements[idx];
    }

    /**
     * 在idx位置设置元素为ele
     *
     * @param idx 索引位置
     * @param ele 元素
     * @return 之前的元素
     */
    public E set(int idx, E ele) {
        if (idx < 0 || idx >= this.size) {
            throw new IndexOutOfBoundsException("Index:" + idx + ", Size:" + this.size);
        }
        E old = this.elements[idx];
        this.elements[idx] = ele;
        return old;
    }

    /**
     * 在idx位置插入一个元素
     *
     * @param idx 索引位置
     * @param ele 元素
     */
    public void insert(int idx, E ele) {
        if (idx < 0 || idx > this.size) {
            throw new IndexOutOfBoundsException("Index:" + idx + ", Size:" + this.size);
        }

        ensureCapacity(this.size + 1);

        for (int i = this.size; i > idx; i--) {
            this.elements[i] = this.elements[i - 1];
        }
        this.elements[idx] = ele;
        this.size++;
    }

    /**
     * 扩容逻辑
     *
     * @param capacity 原容量
     */
    private void ensureCapacity(int capacity) {
        int oldCap = this.elements.length;
        if (oldCap >= capacity) {
            return;
        }
        int newCap = oldCap + (oldCap >> 1);
        E[] newElements = (E[]) new Object[newCap];
        for (int i = 0; i < this.size; i++) {
            newElements[i] = this.elements[i];
        }
        this.elements = newElements;

        System.out.println(oldCap + "扩容为" + newCap);
    }

    /**
     * 删除idx位置的元素
     *
     * @param idx 索引位置
     * @return 被删除的元素
     */
    public E remove(int idx) {
        if (idx < 0 || idx >= this.size) {
            throw new IndexOutOfBoundsException("Index:" + idx + ", Size:" + this.size);
        }
        E old = this.elements[idx];
        for (int i = idx + 1; i < this.size; i++) {
            this.elements[i - 1] = this.elements[i];
        }
        this.elements[--this.size] = null;
        return old;
    }

    public E remove(E ele) {
        return remove(indexOf(ele));
    }

    /**
     * 查看索引位置
     *
     * @param ele 元素
     * @return 索引位置
     */
    public int indexOf(E ele) {
        if (ele == null) {
            for (int i = 0; i < this.size; i++) {
                if (this.elements[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < this.size; i++) {
                if (ele.equals(this.elements[i])) {
                    return i;
                }
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size = ").append(this.size).append(", [");
        for (int i = 0; i < this.size; i++) {
            if (i != 0) {
                sb.append(", ");
            }
            sb.append(this.elements[i]);
        }
        sb.append("]");
        return sb.toString();
    }

    @Override
    protected void finalize() throws Throwable {
        super.finalize();
        System.out.println("gc....");
    }
}
